package com.tim.test.leetcode.simulation.huawei;

import com.alibaba.fastjson.JSON;
import org.junit.Test;

import java.util.*;

public class Simulation1 {

    @Test
    public void test(){
        Object r = null;
//        r = getMatchNum(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 2, 1});// 匹配的二元组数量
//        r = getMatchNum(new int[]{1, 2, 4, 4, 2, 1}, new int[]{3, 2, 1});
//        r = findNearest(new int[][]{{0,3,5,4,2},
//                {2,5,7,8,3},
//                {2,5,4,2,4}});// 最小距离
//        r = reverse("yM eman si boB.");// 单词倒序
//        r = reverse("woh era uoy ? I ma enif.");
        calKArr("1 2 3 1 2 3 1", 2);// k优雅数组
        System.out.println(JSON.toJSONString(r));
    }

    // 二元组个数
    // map or array存储数值个数，笛卡尔积
    public int getMatchNum(int[] arr1, int[] arr2){
        int num = 0;
        int[] numTimes1 = new int[100000];
        int[] numTimes2 = new int[100000];
        for (int i =0; i < arr1.length; i++) {
            numTimes1[arr1[i]]=numTimes1[arr1[i]]+1;
        }
        for (int i =0; i < arr2.length; i++) {
            numTimes2[arr2[i]]=numTimes2[arr2[i]]+1;
        }
        for (int i =0; i < numTimes1.length; i++) {
            num +=numTimes1[i]*numTimes2[i];
        }
        return num;
    }

    // 最近距离
    // map存val-坐标；遍历求最小
    public int[][] findNearest(int[][] arrs){
        int[][] results = new int[arrs.length][arrs[0].length];
        for (int i = 0; i < arrs.length; i++) {
            Arrays.fill(results[i], -1);
        }
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int i =0; i < arrs.length; i++) {
            for (int j = 0; j < arrs[0].length; j++) {
                if(!map.containsKey(arrs[i][j])){
                    List<int[]> list = new ArrayList<>();
                    map.put(arrs[i][j], list);
                }
                map.get(arrs[i][j]).add(new int[]{i, j});
            }
        }

        for (Integer key : map.keySet()){
            final List<int[]> ints = map.get(key);
            if(ints.size()>1){
                for (int i = 0; i < ints.size(); i++){
                    final int[] ints1 = ints.get(i);
                    int min = Integer.MAX_VALUE;
                    for (int j = 0; j < ints.size(); j++) {
                        if(j==i){
                            continue;
                        }
                        final int[] ints2 = ints.get(j);
                        int temp = Math.abs(ints1[0]-ints2[0])+Math.abs(ints1[1]-ints2[1]);
                        if(temp<min){
                            min = temp;
                            results[ints1[0]][ints1[1]]=min;
                            if(min==1){
                                break;
                            }
                        }
                    }
                }
            }
        }
        return results;
    }

    // 单词倒序
    // 对单词字符，入栈，遇非单词字符，出栈拼接
    public String reverse(String str){
        final char[] chars = str.toCharArray();
        StringBuilder builder = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i =0; i <chars.length; i++) {
            final char aChar = chars[i];
            if(aChar!=' ' && aChar!='.' && aChar!='?' && aChar!=','){
                stack.push(aChar);
            }else{
                while(!stack.isEmpty()){
                    builder.append(stack.pop());
                }
                builder.append(aChar);
            }
        }
        while(!stack.isEmpty()){
            builder.append(stack.pop());
        }
        return builder.toString();
    }

    // 滑动窗口向右探索，探索到满足条件的最小元数组k时，记录左右下标。
    // 线性连续添加剩余元素，Map<start, Set<end>>去重
    // 数组记录元素个数，下标定位，探索新数值时下标定位值+1；
    public void calKArr(String str, int k){
        Integer[] nums = Arrays.stream(str.trim().split("\\s+"))
                .map(Integer::valueOf)
                .toArray(Integer[]::new);
        List<int[]> indexList = new ArrayList<>();
        int length = nums.length;
        int[] valTimes = new int[length];
        int start = 0;
        for (int i = 0; i < length; i++) {
            int val = nums[i];
            valTimes[val]++;
            if((valTimes[val]==k)){
                while(valTimes[val]==k && start<=i){
                    int temp = nums[start];
                    valTimes[temp]--;
                    start++;
                }
                indexList.add(new int[]{start-1, i});
            }
        }
        if(indexList.size()==0){
            System.out.println(0);
            return;
        }
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int arrNums = 0;
        for(int[] indexs : indexList){
            int arrStart = indexs[0];
            int arrEnd = indexs[1];
            for (int i = arrStart; i >=0 ; i--) {
                if(!map.containsKey(i)){
                    map.put(i, new HashSet<>());
                }
                Set<Integer> iEndSet = map.get(i);
                for (int j = arrEnd; j < length; j++) {
                    if(iEndSet.add(j)){
                        arrNums++;
                    }
                }
            }
        }
        System.out.println(arrNums);
    }


}
